Computer graphics design generally consists of instructions implemented via a graphics program on a computer system. The instructions are used to specify the calculations and operations needed to produce three-dimensional displays. OpenGL by Silicon Graphics, Inc., of Mountain View, Calif., exemplifies a system of graphics instructions used by graphics designers and artists.
Computer graphics design can be envisioned as a pipeline through which data pass, where the data are used to define the image to be produced and displayed. At various points along the pipeline, various calculations and operations are specified by the graphics designer, and the data are modified accordingly.
In the initial stages of the pipeline, the desired image is framed using geometric shapes such as lines and polygons, referred to in the art as “primitives.” The derivation of the vertices for an image and the manipulation of the vertices to provide animation entail performing numerous geometric calculations in order to project the three-dimensional world being designed to a position in the two-dimensional world of the display screen.
Primitives are then decomposed into “fragments,” and these fragments are assigned attributes such as color, perspective, and texture. In order to enhance the quality of the image, effects such as lighting, fog, and shading are added, and anti-aliasing and blending functions are used to give the image a smoother and more realistic appearance. In the final stage, the fragments and their associated attributes are stored in the framebuffer as pixels. The pixel values can be later read from the framebuffer, and can be used to display images on the computer screen.
The processes pertaining to assigning colors, depth, texturing, lighting, etc., are collectively known as rendering. The specific process of determining per-pixel or per-fragment values from input geometric primitives is known as rasterization.
With reference now to Prior Art FIG. 1, process 130 exemplifies one embodiment of a graphics design process implemented using a graphics program on a computer system. Process 130 enables the designer to produce three-dimensional images using different computer systems and processors. Process 130 operates on vertex (or geometric) data 131. The process stages within process 130 consist of display list 133, evaluators 134, per-vertex operations and primitive assembly 135, rasterization 138, per-fragment operations 139, and framebuffer 140.
Vertex data 131 are loaded from the computer system's memory and saved in display list 133; however, in some graphics programs, a display list is not used and, instead, the vertex data are processed immediately. When display list 133 is executed, evaluators 134 derive the coordinates, or vertices, that are used to describe points, lines, polygons, and the like (e.g., primitives). All geometric primitives are eventually described by collections of vertices.
With reference still to Prior Art FIG. 1, in per-vertex operations and primitive assembly 135, vertex data 131 are converted into primitives that are assembled to represent the surfaces to be graphically displayed. Some vertex data (for example, spatial coordinates) are transformed, typically using matrix multiplication, to project the spatial coordinates from a position in the three-dimensional world to a position on the display screen. In addition, advanced features are also performed in per-vertex operations and primitive assembly 135. Texturing coordinates may be generated and transformed. Lighting calculations are performed using the transformed vertex, the surface normal, material properties, and other lighting information to produce a color value. Perspective division, which is used to make distant objects appear smaller than closer objects in the display, also occurs in per-vertex operations and primitive assembly 135.
Rasterization 138 is the conversion of vertex data into “fragments.” Each fragment corresponds to a single element (e.g., a “pixel”) in the graphics display, and typically includes data defining color, shading, and texture. Per-fragment operations 139 consist of additional operations that may be enabled to enhance the detail of the fragments, such as blending, dithering and other like operations. After completion of these operations, the processing of the fragment is complete and it is written as a pixel to framebuffer 140.
Process 130 and other prior art computer graphics processes can be accomplished in software, in hardware (e.g., processors, integrated circuits, “chips,” etc.), or in a combination of hardware and software. As hardware becomes more sophisticated and less expensive to produce, it is becoming more cost-beneficial to perform computer graphics processes (such as the rendering process) in hardware using specialized chips or collections of chips.
Hardware used for computer graphics is generally focused on a limited set of objects and object types, such as points, lines, triangles, and quadrangles (“quads”). In using these objects to render a scene, prior art graphics systems (such as the aforementioned OpenGL system) gain some efficiency by reusing vertices from one primitive to form a second, adjacent primitive. For example, three vertices can be used to form a first triangle primitive. A triangle primitive adjacent to the first one can be formed by reusing two of the vertices from the first triangle primitive and adding a new vertex. Similarly, a first quad primitive can be formed using four vertices, and a second quad primitive adjacent to the first can be formed by reusing two of the vertices from the first and adding two new vertices. These steps can be repeated to form triangle meshes, triangle strips, and triangle fans when adjacent triangles are present, and quad strips when adjacent quads are present.
Rendering using quadrangles can provide improvements in performance and efficiency relative to rendering that is limited to a single triangle at a time, because with a quadrangle more edges and vertices are processed per primitive. For example, with quad-based rendering, four vertices and four edges are processed per primitive, versus three vertices and three edges per primitive in triangle-based rendering. In the prior art, specialized chips that support quad-based rendering may be used to further improve processing performance and efficiency relative to those chips which are triangle-based. A quad-based rendering system using these specialized chips has the functionality to process objects other than quadrangles, such as triangles. However, as noted above, a prior art quad-based rendering system can still only process three vertices and three edges at a time when processing a non-quadrangle primitive.
Hence, a disadvantage to the prior art is that the performance capabilities of a quad-based rendering system are not fully realized when processing databases that are based on connected triangles, including triangle fans, strips and meshes. As scenes to be rendered get increasingly more complex and, correspondingly, the size of the triangle primitives gets smaller and smaller, the performance inefficiency associated with processing triangle objects in a quad-based rendering system becomes even more conspicuous.
Accordingly, what is needed is a method or system that can more efficiently process connected-triangle-based databases such as those used in computer graphics. In addition, what is needed is a method or system that accomplishes the above needs and can be used to enhance a quad-based rendering system. The present invention provides a novel solution to these needs. These and other objects and advantages of the present invention will become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.